package solution;

import common.TreeNode;
import solution.design.Solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-10-29 15:47
 */
public class Solution_12BFS {

    /* ===========================================================================================================================
     * 111. 二叉树的最小深度
     * 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * */
    public int minDepth(TreeNode root) {
        if (root==null) return 0;
        //只需要队列，不需要visited，二叉树没有回头路
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        // root 本身就是一层，depth 初始化为 1
        int levelNum=1;
        while (!queue.isEmpty()){
            int size= queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur=queue.poll();
                if (cur.left==null&&cur.right==null){
                    //找到target
                    return levelNum;
                }
                /* 将 cur 的相邻节点加入队列 */
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null)
                    queue.offer(cur.right);
            }
            levelNum++;
        }
        return levelNum;
    }


    /* ===========================================================================================================================
     * 752. 打开转盘锁
     * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
     * 每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
     * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
     * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
     * */
    String plusOne(String s,int j){
        char[] ch=s.toCharArray();
        if (ch[j]=='9')
            ch[j]='0';
        else
            ch[j]++;
        return new String(ch);
    }
    String minusOne(String s,int j){
        char[] ch=s.toCharArray();
        if (ch[j]=='0')
            ch[j]='9';
        else
            ch[j]--;
        return new String(ch);
    }

    public int openLock1(String[] deadends, String target) {
        //set记录需要跳过的死亡密码
        Set<String> dead=new HashSet<>();
        for (String s:deadends) {
            dead.add(s);
        }

        //记录已经穷举过的密码
        Set<String> visited=new HashSet<>();
        Queue<String> queue=new LinkedList<>();
        // 从起点开始启动广度优先搜索
        int step=0;
        queue.offer("0000");
        visited.add("0000");
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                String cur=queue.poll();
                //判断是否是到达终点
                if (dead.contains(cur))
                    continue;
                if (cur.equals(target))
                    return step;

                //遍历相邻节点
                for (int j = 0; j < 4; j++) {
                    String up=plusOne(cur,j);
                    if (!visited.contains(up)){
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down=minusOne(cur,j);
                    if (!visited.contains(down)){
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    //双向BFS优化
    public int openLock(String[] deadends, String target) {
        //set记录需要跳过的死亡密码
        Set<String> dead=new HashSet<>();
        for (String s:deadends) {
            dead.add(s);
        }

        //记录已经穷举过的密码
        Set<String> visited=new HashSet<>();
        //用set不用队列，快速判断是否存在
        Set<String> set1=new HashSet<>();
        Set<String> set2=new HashSet<>();

        // 从起点开始启动广度优先搜索
        int step=0;
        set1.add("0000");  //set1从头开始
        set2.add(target);  //set2从结尾开始
        //visited.add("0000");
        while (!set1.isEmpty()&&!set2.isEmpty()){
            // 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
            Set<String> temp=new HashSet<>();

            /* 将 set1 中的所有节点向周围扩散 */
            for (String cur:set1) {
                if (dead.contains(cur))
                    continue;
                if (set2.contains(cur))
                    return step;
                visited.add(cur);
                for (int i = 0; i < 4; i++) {
                    String up=plusOne(cur,i);
                    if (!visited.contains(up)){
                        temp.add(up);
                    }
                    String down=minusOne(cur,i);
                    if (!visited.contains(down)){
                        temp.add(down);
                    }
                }
            }
            step++;
            // temp 相当于 set1
            // 这里交换 set1 set2，下一轮 while 就是扩散 set2
            set1=set2;
            set2=temp;
        }
        return -1;
    }



    /* ===========================================================================================================================
     * 773. 滑动谜题
     * 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
     * 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
     * 思路：每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列…… 当第一次到达target时，就得到了赢得游戏的最少步数。
     * */
    public void swap(char[] array, int x, int y) {
        char temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
    public int slidingPuzzle(int[][] board) {
        // 记录一维字符串的相邻索引
        int[][] neighbor={
                { 1, 3 },
                { 0, 4, 2 },
                { 1, 5 },
                { 0, 4 },
                { 3, 1, 5 },
                { 4, 2 }};
        int m=2,n=3;
        StringBuilder sb= new StringBuilder();
        String start="";
        String target="123450";
        // 将 2x3 的数组转化成字符串
        for (int i = 0; i <m ; i++) {
            for (int j = 0; j <n ; j++) {
                sb.append(board[i][j]);
            }
        }
        start=sb.toString();
        /*开始BFS框架*/
        Queue<String> queue=new LinkedList<>();
        Set<String> visited=new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int step=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                String cur=queue.poll();
//                System.out.println("curS="+cur);
                //判断是否到达目标
                if (target.equals(cur))
                    return step;
                //开始找到数字0的索引，查询他的邻居
                assert cur != null;
                int index=cur.indexOf('0');
//                System.out.println("index="+index);
                for (int abj:neighbor[index]) {
//                    System.out.println("abj="+abj);
                    String new_board=cur;
                    char[] curChars = new_board.toCharArray();
                    swap(curChars,index,abj);
                    new_board= new String(curChars);
//                    System.out.println("new_board="+new_board);
                    if (!visited.contains(new_board)){
                        queue.offer(new_board);
                        visited.add(new_board);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] board = {{1,2,3},{4,0,5}};
        Solution_12BFS obj=new Solution_12BFS();
        System.out.println(obj.slidingPuzzle(board));
    }

}
